package prac6;
/**
 * Sorted generic list data type implemented as an extension of an abstract 
 * linked list LinkedList<T>
 * 
 * @author          Maria Garcia de la Banda
 * @modified        Brendon Taylor (July 2009) - JavaDoc / Indentation / Style
 *                  Brendon Taylor (Feb 2010) - JavaDoc
 *                  Maria (March 2011) - Hierarchy + Interfaces
 * @param           <T> type of data that can be stored in this list 
 * @since           July 2006
 * @modified        March 2011
 * @input           none
 * @output          only for regression testing
 * @errorHandling   none
 * @knownBugs       none
 */

/* 
 * NOTE: Could also redefine any method in the abstract that uses linear
 * search (like findItem(T thisItem), and deleteItem(T thisItem) to take into
 * account the fact that the list is sorted
 * 
 * New invariants for the class:
 *    (N) if node N points to node N', N.item is less or equal than N'
 */
public class SortedLinkedList<T extends Comparable<T>> extends LinkedList<T> {
    /**
     * Creates an empty object of the class, i.e., an empty list of T items. 
     * Since the list is implemented with nodes, the size is not needed.
     * 
     * @complexity  best and worst case: O(1) 
     */
    public SortedLinkedList() {
	super();
    }

    /**
     * Inserts a new node with newItem to the list, making sure it is inserted 
     * before the first node whose item is greater or equal than newItem.
     * 
     * @param       newItem to add to the list 
     * @post        a new node with newItem appears in the list
     * @complexity  best case (first place) O(1)*O_compare where O_compare
     *              will typically be O(M) where M is the length of newItem
     *              worst case (in last place) O(N)*O_compare, where N is the 
     *              length of the list
     */
     public void add(T newItem) {
         Node current = head;
	 Node previous = null;
	 while (current != null &&
                current.item.compareTo(newItem)<0) {
	     previous = current;
	     current = current.successor;
	 }
	 Node temp = new Node(newItem,current);
	 if (previous == null) { // first element
	     head = temp;
         } else {                  //middle or last element
	     previous.successor = temp;
	 }
	 if (current == null) { // last element
              last = temp;
	 } 
	 length++;
      }
    /*********************** REGRESSION TESTING CODE **********************/

    /**
     * Two test cases: empty lists and non-empty lists. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     */
    private static void testIsEmpty() {  
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        System.out.println("TESTING isEmpty()");
        System.out.println("Expected true, got " + myList.isEmpty());
        myList.add(9);
        System.out.println("Expected false, got " + myList.isEmpty());
        myList.add(0);
        System.out.println("Expected false, got " + myList.isEmpty());
        myList.add(1);
        myList.add(2);
        myList.add(14);
        System.out.println("Expected false, got " + myList.isEmpty());
    }

    /**
     * Two test cases: full lists and non-full lists. 
     * Boundary analysis gives three cases: 0 elements, 1, and many (5).
     */
    private static void testIsFull() {
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        System.out.println("TESTING isFull()");
        System.out.println("Expected false, got " + myList.isFull());
        myList.add(9);
        System.out.println("Expected false, got " + myList.isFull());
        myList.add(0);
        myList.add(1);
        myList.add(2);
        myList.add(14);
        System.out.println("Expected false, got " + myList.isFull());
    }

    /**
     * One test case: adding to a list of any length. 
     * Boundary analysis gives three cases: 0 elements, 1, and many (5).
     */
    private static void testAdd() {         
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        System.out.println("TESTING add()");
        myList.add(0);
        System.out.println("Expected 0, got " + myList);
        myList.add(9);
        System.out.println("Expected 0 9, got " + myList);
        myList.add(1);
        myList.add(14);
        myList.add(20);
        System.out.println("Expected 0 1 9 14 20, got " + myList);
    }


    /**
     * Two test cases: the item is not in the list and it is in it. 
     * Subclasses for the class in which the item is in: is the first slot 
     *       the last, or in the middle.
     * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
     *       used-1, and some slot in the middle.
     * 
     * @throws      Exception thrown when list is full
     */
    private static void testDeleteItem() throws Exception {         
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        myList.add(8);
        myList.add(7);
        myList.add(5);
        myList.add(5);
        myList.add(4);
        myList.add(3);
        myList.add(2);
        myList.add(1);
        myList.add(0);
        System.out.println("TESTING deleteItem()");
        System.out.println("Expected true, got " + myList.deleteItem(5));
        System.out.println("    with list 0 1 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(1));
        System.out.println("    with list 0 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(0));
        System.out.println("    with list 2 3 4 5 7 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(7));
        System.out.println("    with list 2 3 4 5 8, got " + myList);
        System.out.println("Expected true, got " + myList.deleteItem(8));
        System.out.println("    with list 2 3 4 5, got " + myList);
        System.out.println("Expected false,  got " + myList.deleteItem(8));
        System.out.println("    with list 2 3 4 5, got " + myList);
    }

    /** 
     * Two test cases: the list is empty and it is not. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     * 
     * @throws      Exception thrown when list is full or empty
     */ 
    private static void testDeleteFirst() throws Exception {
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        myList.add(4);
        myList.add(3);
        myList.add(2);
        myList.add(1);
        myList.add(0);
        System.out.println("TESTING deleteFirst()");
        System.out.println("Expected 0, got " + myList.deleteFirst());
        System.out.println("    with list 1 2 3 4, got " + myList);
        myList.deleteFirst();
        myList.deleteFirst();
        System.out.println("Expected 3, got " + myList.deleteFirst());
        System.out.println("    with list 4, got " + myList);
        System.out.println("Expected 4, got " + myList.deleteFirst());
        System.out.println("    with list , got " + myList);
        System.out.print("Expected exception ");
        
        try {
                myList.deleteFirst();
        }
        catch(Exception e) {
                System.out.println(e);
                return;
        }

        System.out.println("but no exception thrown");
    }

    /**
     * Two test cases: the list is empty and it is not. 
     * Boundary analysis gives four cases: 0 elements, 1, 2, and many (5).
     * 
     * @throws      Exception thrown when list is full or empty
     */
    private static void testDeleteLast() throws Exception {
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        myList.add(4);
        myList.add(3);
        myList.add(2);
        myList.add(1);
        myList.add(0);
        System.out.println("TESTING deleteLast()");
        System.out.println("Expected 4, got " + myList.deleteLast());
        System.out.println("    with list 0 1 2 3, got " + myList);
        myList.deleteLast();
        myList.deleteLast();
        System.out.println("Expected 1, got " + myList.deleteLast());
        System.out.println("    with list 0, got " + myList);
        System.out.println("Expected 0, got " + myList.deleteLast());
        System.out.println("    with list , got " + myList);
        System.out.print("Expected exception ");
        
        try {
                myList.deleteLast();
        }
        catch(Exception e) {
                System.out.println(e);
                return;
        }
        
        System.out.println("but no exception thrown");
    }

    /**
     * Two test cases: the item is not in the list and it is in it. 
     * Subclasses for the class in which the item is in: is the first slot 
     *       the last, or in the middle. 
     * Boundary analysis gives five cases: slot 0, slot 1, slot used-2, slot 
     *       used-1, and some slot in the middle.
     */
    private static void testFind() {        
        SortedLinkedList<Integer> myList = new SortedLinkedList<Integer>();
        myList.add(0);
        myList.add(1);
        myList.add(2);
        myList.add(14);
        myList.add(20);
        myList.add(30);
        myList.add(40);
        myList.add(50);
        System.out.println("TESTING find()");
        System.out.println("Expected false, got " + myList.find(9));
        System.out.println("Expected true, got " + myList.find(0));
        System.out.println("Expected true, got " + myList.find(1));
        System.out.println("Expected true, got " + myList.find(14));
        System.out.println("Expected true, got " + myList.find(40));
        System.out.println("Expected true, got " + myList.find(50));
    }
    
    /**
     * @param       args command-line arguments
     */
    public static void main(String[] args) {
        
        try{   
            testIsEmpty();
            testIsFull();
            testAdd();
            testDeleteItem();
            testDeleteFirst();
            testDeleteLast();
            testFind();
        }
        catch(Exception e) {
            System.out.println(" Error, unexpected exception: "+e);
        }
    }
}